package com.cn.algorithm02.class06;

import com.cn.algorithm02.class01.CodeUtil;
import com.sun.org.apache.regexp.internal.RE;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/***
 * @author: hels
 * @description:快速排序：时间复杂度O(N)，
 **/
public class C03_QuickSort2 {
    public static void main(String[] args) {
//        int[] arr = CodeUtil.generatorArray();
////        quick2(arr);
//        quick2(arr, 0, arr.length-1);
//
//        System.out.println("===");
//        CodeUtil.printArray(arr);

        int num = 0;
        for (int i = 0; i < 10_000; i++) {
            int[] arr = CodeUtil.generatorArray(false);
            int[] dz = CodeUtil.copyArr(arr);
            quick(arr, 0, arr.length-1);
//            quick1(arr, 0, arr.length-1);
            Arrays.sort(dz);
            boolean b = CodeUtil.compareArr(arr, dz);
            if (b) {
                num++;
            }
            double random = Math.random();
        }
        System.out.println(num);


    }

    /*
    小于左边，基准数中间，大于右边。基准数为最右边
     */
    public static void quick1(int[] arr,int L, int R) {
        if(arr == null || arr.length < 2) {
            return ;
        }

        process(arr, L, R);
    }

    public static void process(int[] arr, int L, int R) {
        // basic case
        if (L >= R) return;

        // 递归划分
        int[] basicArr = landsFlag(arr, L, R);
        // 核心代码
        process(arr, L, basicArr[0]-1);
        process(arr,basicArr[1]+1, R);
    }

    /**
     * 单次的随机快速排序
     */
    public static int[] landsFlag(int[] arr, int L, int R) {
        // length >=2
        int basic = arr[new Random().nextInt(R-L+1) + L]; // 选取一个随机数作为基数
        int left = L-1;
        int right = R+1;
        int pointer = L;
        //
        while (pointer < right) {
            if (arr[pointer] < basic) {
                CodeUtil.swap(arr, pointer++, ++left);
            } else if (arr[pointer] > basic) {
                CodeUtil.swap(arr,pointer, --right);
            } else {
                pointer++;
            }
        }
        return new int[]{left+1, right-1};
    }

    // 非递归实现快排

    /**
     * 该类用于记录每次排序的范围
     */
    public static class Op {
        int l;
        int r;
        public Op(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }

    /**
     * 思路解读：
     * 1、Op类是辅助类，用于计算排序范围
     * 2、landsFlag(arr, L, R)会将LR范围内根据某个随机数，小于，等于，大于排序，并返回等于元素的首尾下标，依次计算小于区和大于区排序范围
     * 3、通过stack记录每次landsFlag排序后左右两侧的排序范围，放在栈中，可以使其空间复杂度为O(logN)
     * 4、重复2,3步骤
     */
    public static void quick(int[] arr, int L, int R) {
        int[] part = landsFlag(arr, L, R);
        Stack<Op> stack = new Stack<>();
        Op op1 = new Op(L, part[0] - 1);
        Op op2 = new Op(part[0] + 1, R);
        stack.add(op1);
        stack.add(op2);

        while (!stack.isEmpty()) {
            Op op = stack.pop();
            if (op.l < op.r) {
                int[] range = landsFlag(arr, op.l, op.r);
                Op op3 = new Op(op.l, range[0] - 1);
                Op op4 = new Op(range[0] + 1, op.r);
                stack.push(op3);
                stack.push(op4);
            }
        }

    }

}
